/*
 * Copyright (c) Huawei Technologies Co., Ltd. 2024-2024. All rights reserved.
 *
 */

/**
 * 树型结构
 */
export class TreeNode<T> {
  key: string;
  value: T;
  children: TreeNode<T>[];

  constructor(key: string, value: T) {
    this.key = key;
    this.value = value;
    this.children = [];
  }
}

export class Tree<T> {
  root: TreeNode<T>;

  constructor(key: string, value: T) {
    this.root = new TreeNode(key, value);
  }

  findNodeByKeyDFS(key: string, node = this.root): TreeNode<T> | undefined {
    if (node.key === key) {
      return node;
    }

    for (const child of node.children) {
      const foundNode = this.findNodeByKeyDFS(key, child);
      if (foundNode) {
        return foundNode;
      }
    }

    return undefined;
  }

  findNodeByKeyBFS(key: string): TreeNode<T> | undefined {
    const queue: TreeNode<T>[] = [this.root];

    while (queue.length) {
      const node = queue.shift()!;
      if (node.key === key) {
        return node;
      }

      queue.push(...node.children);
    }

    return undefined;
  }

  findParentNodeByKey(key: string): TreeNode<T> | undefined {
    const queue: [TreeNode<T>, TreeNode<T> | undefined][] = [[this.root, undefined]];

    while (queue.length) {
      const [node, parent] = queue.shift()!;
      if (node.key === key) {
        return parent;
      }

      for (const child of node.children) {
        queue.push([child, node]);
      }
    }

    return undefined;
  }

  addNode(key: string, value: T, parentKey: string): boolean {
    const parentNode = this.findNodeByKeyBFS(parentKey);
    if (!parentNode) {
      return false;
    }

    const newNode = new TreeNode(key, value);
    parentNode.children.push(newNode);
    return true;
  }
}
